// 2025/3/3
// https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked
// 滑动窗口的最大值

// set
class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            map<int, int> mp;
            vector<int> ans;
            int n = nums.size();
            for(int i = 0; i < k; i++) ++mp[nums[i]];
            ans.emplace_back((--mp.end())->first);
            for(int i = 0; i < n - k; i++)
            {
                --mp[nums[i]];
                if(mp[nums[i]] == 0) mp.erase(nums[i]);
                ++mp[nums[i + k]];
                ans.emplace_back((--mp.end())->first);
            }
            return ans;
        }
    };

// priority_queue
class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> ans;
            priority_queue<pair<int, int>> prq;
            int n = nums.size();
            for(int i = 0; i < k; i++) prq.emplace(nums[i], i);
            ans.emplace_back(prq.top().first);
    
            for(int i = k; i < n; i++)
            {
                prq.emplace(nums[i], i);
                while(prq.top().second <= i - k) prq.pop();
                ans.emplace_back(prq.top().first);
            }
            return ans;
        }
    };

// deque
class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> ans;
            int n = nums.size();
            deque<int> q;
            for(int i = 0; i < n; i++)
            {
                if(!q.empty() && i >= k && nums[i - k] == q.front())
                    q.pop_front();
                while(!q.empty() && q.back() < nums[i])
                    q.pop_back();
                q.emplace_back(nums[i]);
    
                if(i >= k - 1)
                    ans.emplace_back(q.front());
            }
            return ans;
        }
    };